11159. Подсчет породы

 

Несколько сезонов жаркого лета и холодной зимы изрядно подпортили изгородь n коров Фермера Джона, которые выстроены в ряд и последовательно пронумерованы от 1 до n. Каждая корова принадлежит к одной из трёх пород: 1 – Holsteins, 2 – Guernseys, 3 – Jerseys. Фермер Джон просит вас посчитать количество коров каждой породы в пределах заданного интервала.

 

Вход. Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 105).

Следующие n строк содержат по одному целому числу 1, 2 или 3 – идентификатор породы соответствующей коровы.

Следующие q строк описывают запросы, каждый из которых состоит из двух целых чисел a, b (a ≤ b).

 

Выход. Для каждого из q запросов (a, b), выведите строку, содержащую три целых числа – количество коров каждой породы на интервале от a до b включительно.

 

Пример входа

Пример выхода

6 3

2

1

1

3

2

1

1 6

3 3

2 4

3 2 1

1 0 0

2 0 1

 

 

РЕШЕНИЕ

частичные суммы

 

Анализ алгоритма

Объявим три целочисленных массива s[i] (1 ≤ i ≤ 3). Префиксные суммы для коров породы i будут содержаться в массиве s[i].

Ответ на запрос (a, b) вычисляется следующим образом:

·        Количество коров породы 1 равно s[1][b] – s[1][a – 1];

·        Количество коров породы 2 равно s[2][b] – s[2][a – 1];

·        Количество коров породы 3 равно s[3][b] – s[3][a – 1];

 

Пример

Для приведенного примера массивы префиксных сумм s[i] (1 ≤ i ≤ 3) будут следующими:

Рассмотрим запрос на интервале (2, 4):

·        Количество коров породы 1 равно s[1][4] – s[1][1] = 2 – 0 = 2;

·        Количество коров породы 2 равно s[2][4] – s[2][1] = 1 – 1 = 0;

·        Количество коров породы 3 равно s[3][4] – s[3][1] = 1 – 0 = 1;

 

Реализация алгоритма

Объявим массивы для хранения частичных сумм.

 

#define MAX 100001

int s[4][MAX];

 

Читаем входные данные.

 

scanf("%d %d", &n, &q);

 

Вычисляем массивы частичных сумм.

 

memset(s, 0, sizeof(s));

for (i = 1; i <= n; i++)

{

  scanf("%d", &x);

  for (j = 1; j <= 3; j++)

    s[j][i] = s[j][i - 1];

  s[x][i]++;

}

 

Последовательно обрабатываем q запросов.

 

for (i = 0; i < q; i++)

{

   scanf("%d %d", &a, &b);

   printf("%d %d %d\n", s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1],

                        s[3][b] - s[3][a - 1]);

}